package org.huawei260.TiKu.C;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Auther: qingle
 * @Date: 2024/10/28-0:16
 * @Description:
 * @version: 1.0
 */
import java.util.*;
public class C_快递员的烦恼 {

//	public class Main {
		static int n; // 客户数量
		static int m; // 客户之间距离信息数量
		static int[][] dist; // 客户之间的距离信息
		static List<Integer>[] graph; // 图的邻接表表示

		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
			n = sc.nextInt();
			m = sc.nextInt();

			dist = new int[1001][1001];
			graph = new ArrayList[1001];

			for (int i = 0; i < 1001; i++) {
				Arrays.fill(dist[i], Integer.MAX_VALUE);
				graph[i] = new ArrayList<>();
			}

			// 读取快递信息
			for (int i = 0; i < n; i++) {
				int customer = sc.nextInt();
				int distance = sc.nextInt();
				dist[0][customer] = distance; // 快递站点到客户的距离
				dist[customer][0] = distance; // 客户到快递站点的距离
			}

			// 读取客户之间的距离信息
			for (int i = 0; i < m; i++) {
				int id1 = sc.nextInt();
				int id2 = sc.nextInt();
				int distance = sc.nextInt();
				dist[id1][id2] = distance;
				dist[id2][id1] = distance;
				graph[id1].add(id2);
				graph[id2].add(id1);
			}

			// 计算最短路径
			int shortestDistance = Integer.MAX_VALUE;
			for (int i = 1; i <= n; i++) {
				int[] pathDistance = new int[1001];
				Arrays.fill(pathDistance, Integer.MAX_VALUE);
				pathDistance[0] = 0;

				boolean[] visited = new boolean[1001];
				dfs(0, i, 0, visited, pathDistance);

				shortestDistance = Math.min(shortestDistance, pathDistance[i]);
			}

			// 输出最短路径距离
			System.out.println(shortestDistance == Integer.MAX_VALUE ? -1 : shortestDistance);
		}

		private static void dfs(int current, int end, int distance, boolean[] visited, int[] pathDistance) {
			if (current == end) {
				pathDistance[end] = Math.min(pathDistance[end], distance);
				return;
			}

			visited[current] = true;
			for (int next : graph[current]) {
				if (!visited[next]) {
					dfs(next, end, distance + dist[current][next], visited, pathDistance);
				}
			}
			visited[current] = false;
		}
//	}
}
